/**
 * \file   barbre.h
 * \author Babinot Alexandre, Guilet Pierre
 *  \version 1.0
 *  \date 24 janvier 2012
 */
#ifndef BARBRE_H
#define BARBRE_H
#include<vector>
#include <iterator>
#include "node.h"
#include "NodeIT.h"
#include "BIterator.h"

template<class T>
class Node;

/**
 *\class BArbre
 *
 * \brief classe permettant de representer un Barbre
 */
template<class T,class Compare>
class BArbre
{
typedef typename std::vector<pNode<T>*>::iterator ItePNode;
typedef NodeIT<T>* PNodeIT;
typedef pNode<T>* PNode;

private:
    Node<T> * root;
    unsigned int order;
    unsigned int hauteur;

public:
    /**
     * \fn BArbre(unsigned int o)
     *  \brief Constructeur d'un nouveau BArbre
     *  \param o ordre du Barbre
     */
    BArbre(unsigned int o);
    
    
    
    /**
     * \fn recupererCle(PNodeIT nodeWithValueToDeleteIT,T key)
     *  \brief récupère la valeur du noeud à supprimer
     *  \param nodeWithValueToDeleteIT noeud contenant la valeur à supprimer
     *  \param key clé que l'on souhaite supprimer
     */    
    void recupererCle(PNodeIT nodeWithValueToDeleteIT,T key);



     /**
     * \fn permuterCle(PNodeIT nodeWithValueToDeleteIT,T key)
     *  \brief permet de permuter la clé à supprimer avec la clé à remonter
     *  \param nodeWithValueToDeleteIT noeud contenant la valeur à supprimer
     *  \param key clé que l'on souhaite supprimer
     */     
    void  permuterCle(PNodeIT nodeWithValueToDeleteIT,T key);



    /**
     * \fn monterCleDuFrereGauche(Node<T>* nodeParent,Node<T>* frereGauche,ItePNode iteToPositionPnodeParent)
     *  \brief permet de ramener la valeur du noeud enfant situé immédiatement sur la gauche par rapport à une clé du noeud parent, à l'intérieur du noeud parent 
     *  \param nodeParent correspond au noeud parent
     *  \param frereGauche récupère le noeud enfant situé immédiatement sur la gauche par rapport à une clé du noeud parent
     *  \param ItePNode correspond à l'itérateur pointant sur la valeur recherchée
     */    
    void monterCleDuFrereGauche(Node<T>* nodeParent,Node<T>* frereGauche,ItePNode iteToPositionPnodeParent);
    
    
    
    /**
     * \fn monterCleDuFrereDroit(Node<T>* nodeParent,Node<T>* frere,ItePNode iteToPositionPnodeParent)
     *  \brief permet de ramener la valeur du noeud enfant situé immédiatement sur la droite par rapport à une clé du noeud parent, à l'intérieur du noeud parent 
     *  \param nodeParent correspond au noeud parent
     *  \param frere récupère le noeud enfant situé immédiatement sur la droite par rapport à une clé du noeud parent
     *  \param ItePNode correspond à l'itérateur pointant sur la valeur recherchée
     */    
    void monterCleDuFrereDroit(Node<T>* nodeParent,Node<T>* frere,ItePNode iteToPositionPnodeParent);
    
    
    
    /**
     * \fn descendreCleDuPereDeFrereGauche(ItePNode pNodeWithValueToDeleteIte,PNodeIT nodeWithValueToDeleteIT)
     *  \brief permet de descendre la valeur d'un noeud du noeud parent après la remontée d'une valeur du fils gauche
     *  \param pNodeWithValueToDeleteIte pNode contenant la clé recherchée
     *  \param nodeWithValueToDeleteIT clé que l'on souhaite supprimer
     */    
    void descendreCleDuPereDeFrereGauche(ItePNode pNodeWithValueToDeleteIte,PNodeIT nodeWithValueToDeleteIT);
    
    
    
    /**
     * \fn descendreCleDuPereDeFrereDroit(ItePNode pNodeWithValueToDeleteIte,PNodeIT nodeWithValueToDeleteIT)
     *  \brief permet de descendre la valeur d'un noeud du noeud parent après la remontée d'une valeur du fils droit
     *  \param pNodeWithValueToDeleteIte pNode contenant la clé recherchée
     *  \param nodeWithValueToDeleteIT clé que l'on souhaite supprimer
     */    
    void descendreCleDuPereDeFrereDroit(ItePNode pNodeWithValueToDeleteIte,PNodeIT nodeWithValueToDeleteIT);
    
    
    
    /**
     * \fn descendreCleDuPere(PNodeIT nodeWithValueToDeleteIT)
     *  \brief permet de descendre la valeur d'un noeud du noeud parent
     *  \param nodeWithValueToDeleteIT clé que l'on souhaite supprimer
     *  \param b
     */    
    void descendreCleDuPere(PNodeIT nodeWithValueToDeleteIT, bool b);
    
    
    
    /**
     * \fn insert(T i)
     *  \brief permet d'insérer une valeur au BArbre
     *  \param i valeur à insérer
     */   
    void insert(T i);
    
    
    
    /**
     * \fn pNode<T>* rechercherKDansNode(T key,ItePNode &it)
     *  \brief effectue une recherche de clé sur l'itérateur et renvoie le pNode correspondant
     *  \param key valeur recherché
     *  \param it itérateur pour accéder à la valeur
     *  \return le pNode recherché
     */   
    pNode<T>* rechercherKDansNode(T key,ItePNode &it);
    
    
    
    /**
     * \fn deleteNode(T key)
     *  \brief effectue une suppression d'une valeur
     *  \param key valeur recherché
     */   
    int deleteNode(T key);
    
    
    
    /**
     * \fn getRoot()
     *  \brief renvoit la racine de l'arbre
     *  \return le noeud de la racine
     */   
    Node<T> * getRoot();
    
    
    
    /**
     * \fn setRoot(Node<T> * r)
     *  \brief actualise la racine de l'arbre
     *  \param r noeud correspondant à la nouvelle racine
     */   
    void setRoot(Node<T> * r);
    
    
    
    /**
     * \fn lookNode(Node<T> * currentNode,T key)
     *  \brief recherche récursivement l'emplacement dans lequel insérer un noeud
     *  \param currentNode Noeud à un instant "t" lors de la récursion
     *  \param T valeur à insérer
     *  \return un noeud cohéretn avec l'itération correspondante
     */   
    PNodeIT lookNode(Node<T> * currentNode,T key);
    
    
    
    /**
     * \fn checkOrder(Node<T> * currentNode)
     *  \brief vérifie l'ordre de l'arbre
     *  \param currentNode noeud en cours de traitement dans l'instance de checkOrder
     */   
    void checkOrder(Node<T> * currentNode);
    
    
    
    /**
     * \fn afficherArbre()
     *  \brief fonction d'affichage de l'arbre
     */   
    void afficherArbre();
    
    
    
    /**
     * \fn visitNode(Node<T>* node, std::vector< std::vector<Node<T>*> > listeDeListeDeNodesParHauteur, unsigned int hauteur)
     *  \brief permet lors de l'affichage d'effectuer récursivement un affichage par hauteur
     *  \param node le noeud en cours
     *  \param listeDeListeDeNodesParHauteur vecteur de hauteur
     *  \param hauteur hauteur en cours
     *  \return retourne le vecteur correspondant à une hauteur
     
     */ 
    std::vector< std::vector<Node<T>*> > visitNode(Node<T>* node, std::vector< std::vector<Node<T>*> > listeDeListeDeNodesParHauteur, unsigned int hauteur);
    
    
    
    /**
     * \fn getHauteur()
     *  \brief récupère la hauteur de l'arbre
     *  \return la hauteur de l'arbre
     */
    unsigned int getHauteur();
    
    
    
    /**
     * \fn getNodeByKeyRec(Node<T> * currentNode, T key)
     *  \brief recherche récursivement un noeud contenant la clé entrée
     *  \param currentNode Noeud en cours de traitement
     *  \param key valeur recherché
     *  \return la valeur recherché
     */   
    PNodeIT getNodeByKeyRec(Node<T> * currentNode,T key);
    
    
    
    /**
     * \fn search(T key)
     *  \brief fonction de recherche de noeud
     *  \return le noeud recherché
     */
    PNodeIT search(T key);
    
    
    
    /**
     * \fn insertNode(T key,ItePNode it)
     *  \brief fonction récursive de comparaison entre deux noeuds
     *  \param T valeur à insérer
     *  \param it itération sur le noeud
     *  \return le noeud recherché
     */
    ItePNode insertNode(T key,ItePNode it);
    
    
    
    /**
     * \fn getFrereGauche(T key,Node<T>* nodeParent,ItePNode iteToPositionPnodeParent)
     *  \brief fonction récursive de comparaison entre deux noeuds
     *  \param nodeParent noeud parent
     *  \param iteToPositionPnodeParent garde en mémoire la position vers lequel le noeud enfant est lié à son parent
     *  \return le frère gauche
     */
    Node<T>* getFrereGauche(Node<T>* nodeParent,ItePNode iteToPositionPnodeParent);
    
    
    
    /**
     * \fn getFrereDroit(T key,Node<T>* nodeParent,ItePNode iteToPositionPnodeParent)
     *  \brief fonction récursive de comparaison entre deux noeuds
     *  \param nodeParent noeud parent
     *  \param iteToPositionPnodeParent garde en mémoire la position vers lequel le noeud enfant est lié à son parent
     *  \return le frère droit
     */
    Node<T>* getFrereDroit(Node<T>* nodeParent,ItePNode iteToPositionPnodeParent);
    
    
    
    /**
     * \fn begin()
     *  \brief renvoie un itérateur sur le premier élément du BArbre
     *  \return un itérateur sur le premier élément du BArbre
     */
    	BNodeIter<T> begin();
    	
    	
    	
    /**
     * \fn end()
     *  \brief renvoie un itérateur sur la fin du Barbre
     *  \return un itérateur sur la fin du Barbre
     */
	BNodeIter<T> end();
};
//commande de compilation : g++ -o Barbre *.c -Wall
//lancement ./Barbre
/*
Pour un Barbre d'ORDRE m, CHAQUE NOEUD CONTIENT k CLES TRIEES AVEC :
m≤ k ≤ 2m (noeud non racine)
1 ≤ k ≤ 2m (noeud racine)
*/
#include <iostream>
#include <stack>
using namespace std;

template<class T,class Compare>
BArbre<T,Compare>::BArbre(unsigned int o)
{
    order=o;
    root=NULL;
}

template<class T,class Compare>
void BArbre<T,Compare>::insert(T key)
{
    //Si l'arbre est vide on ajoute la valeur dans un nouveau k d'un nouveau Node
    if (root==NULL)
    {
        pNode<T>* pNodeRoot = new pNode<T>(key);
        root= new Node<T>(pNodeRoot);
        //Sinon on se déplace dans le bon node et on insère le pNode (contenant la valeur et le pointeur gauche) au bon endroit du vector de pNode
    }
    else
    {

        PNodeIT NodetoAdd;
        //bool trouveEmplacement=0;
        //int indexInsertion=-1;
        int indexInsertion;
        NodetoAdd = lookNode(root,key);
        indexInsertion = distance( NodetoAdd->getNode()->getPNodesVector().begin(),NodetoAdd->getIter());
        NodetoAdd->getNode()->addNodeToIndex(indexInsertion,key);
        checkOrder(NodetoAdd->getNode());


    }

}



template<class T,class Compare>
NodeIT<T>* BArbre<T,Compare>::lookNode(Node<T> * currentNode,T key)
{
    typename vector<pNode<T>*>::iterator it;

    it = currentNode->getPNodesVector().begin();

    //Cas où on arrive a tout noeud avant le pNode empty.

    //iteration sur les noeuds et renvoi du noeud intéressant.
    it=insertNode(key,it);
    //utilisation du iterator pour vérifier si on doit continuer plus bas ou si on est à une feuille
    if((*it)==0)
    {
        return NULL;
    }

    if( (*it)->getPointeur()==0)
    {
        //Cas où le pointeur gauche du Node est null

        //on insère à l'index de l'avant derniere place du vecteur de pNode soit juste avant le pNode empty. Comme size() compte à partir de 1, on fait -1 puis -1 pour l'avant dernier
        //distance permet de détecter quel est la distance entre deux itérateurs et donc l'index recherché.
        return new NodeIT<T>(currentNode,it);
    }
    else
    {
        //Cas où le pointeur n'est pas null
        return lookNode((*it)->getPointeur(),key);
    }

}

template<class T,class Compare>
typename vector<pNode<T>*>::iterator BArbre<T,Compare>::insertNode(T key,ItePNode it)
{
Compare P;
    if(  P((*it)->getValeur(),key) || (*it)->getValeur()==(T) -1)
    {

        return it;
    }
    else
    {
        it++;
        if(*(it)==0)
        {
            return it;
        }
        return insertNode(key,it);
    }
}

template<class T,class Compare>
pNode<T>* BArbre<T,Compare>::rechercherKDansNode(T key,ItePNode &it)
{

Compare P;
    /*On s'arrête quand on à checker tous les pNode ou qu'on à dépassé la position maximum de la clé*/
    if(  P((*it)->getValeur(),key) || (*it)->getValeur()==(T)-1)
    {
        return 0;
    }
    else
    {
        /*On a trouvé k dans ce node, on renvoit donc le node.*/
        if((*it)->getValeur()==key)
        {
            return (*it);
        }
        /*k n'est pas dans ce node, on cherche donc dans les fils de ce node.*/
        it++;
        if(*(it)==0)
        {
            return 0;
        }
        return rechercherKDansNode(key,it);
    }
}

template<class T,class Compare>
NodeIT<T>* BArbre<T,Compare>::getNodeByKeyRec(Node<T> * currentNode,T key)
{
    typename vector<pNode<T>*>::iterator it;
    pNode<T>* nodeFound;
    PNodeIT researchNode=NULL;
    it = currentNode->getPNodesVector().begin();

    //Cas où on arrive a tout noeud avant le pNode empty.

    //iteration sur les noeuds et renvoi du noeud intéressant.
    nodeFound=rechercherKDansNode(key,it);

    /*On réinitialise l'itérateur à la première position*/
    //it = currentNode->getPNodesVector().begin();
    /*On renvoie le node en cours si k y  est contenu*/
    if(nodeFound)
    {
        return new NodeIT<T>(currentNode,it,nodeFound);
        /*K n'étant pas contenu dans ce node, on cherche dans les fils*/
    }
    else
    {
        it = currentNode->getPNodesVector().begin();

        while(it!=currentNode->getPNodesVector().end() && researchNode==NULL)
        {
            if( (*it)->getPointeur()!=0)
            {
                researchNode= getNodeByKeyRec((*it)->getPointeur(),key);
            }
            it++;
        }
    }
    /*On a finis de chercher dans les fils et ce  node ne contient pas k, on retourne donc null*/
    return researchNode;

}

template<class T,class Compare>
void BArbre<T,Compare>::checkOrder(Node<T> * currentNode)
{
    if(  order>currentNode->getPNodesVector().size()-1 && currentNode->getParent()!=NULL  )
    {
        //TODO pour gérer l'ordre lors de la suppression!


    }
    if(2*order<currentNode->getPNodesVector().size()-1)
    {
        unsigned int indexLeft=(currentNode->getPNodesVector().size()-1)/2;
        //int indexRight=currentNode->getPNodesVector().size()-indexLeft;
        pNode<T>* pNodeNode = new pNode<T>((currentNode->getPNodesVector().at(0))->getValeur());
        Node<T> * n1 = new Node<T>(pNodeNode);
        unsigned int i=1;
        while (i<indexLeft)
        {
            pNodeNode = new pNode<T>((currentNode->getPNodesVector().at(i))->getValeur());
            n1->addNodeToIndex(i,(currentNode->getPNodesVector().at(i))->getValeur());
            i++;
        }
        int i_parent=i;
        i++;
        pNodeNode = new pNode<T>((currentNode->getPNodesVector().at(i))->getValeur());
        Node<T> * n2 = new Node<T>(pNodeNode);
        i++;
        int j=1;
        while (i<currentNode->getPNodesVector().size())
        {
            //pNode* pNodeNode = new pNode((currentNode->getPNodesVector().at(i))->getValeur());
            if((currentNode->getPNodesVector().at(i))->getValeur()!=-1)
            {

                n2->addNodeToIndex(j,(currentNode->getPNodesVector().at(i))->getValeur());
            }
            i++;
            j++;

        }
        i=i_parent;
        //DONE cas où le parent est nul. et rajout du parent dans les noeuds n1 et N2
        if(currentNode->getParent()==NULL)
        {
            Node<T> * NodeParent= new Node<T>(new pNode<T>((currentNode->getPNodesVector().at(i))->getValeur()));
            NodeParent->getPNodesVector().at(0)->setPointeur(n1);
            NodeParent->getPNodesVector().at(1)->setPointeur(n2);
            n1->setParent(NodeParent);
            n2->setParent(NodeParent);
            root=NodeParent;
            delete currentNode;
//currentNode
        }
        else
        {
            typename vector<pNode<T>*>::iterator it;
            Node<T> * P=currentNode->getParent();
            it = P->getPNodesVector().begin();

            int indexInsertion;
            //iteration sur les noeuds et renvoi du noeud intéressant.
            it=insertNode((currentNode->getPNodesVector().at(i))->getValeur(),it);

            indexInsertion = distance( (P)->getPNodesVector().begin(),it);
            (P)->addNodeToIndex(indexInsertion,(currentNode->getPNodesVector().at(i))->getValeur());
            (P)->getPNodesVector().at(indexInsertion)->setPointeur(n1);
            (P)->getPNodesVector().at(indexInsertion+1)->setPointeur(n2);
            n1->setParent(P);
            n2->setParent(P);
            i++;
            delete currentNode;
//currentNode
            checkOrder(P);
        }

        //TODO supprimer l'ancien noeud malforme
    }
}

template<class T,class Compare>
void BArbre<T,Compare>::afficherArbre()
{
    vector< vector<Node<T>*> > listeDeListeDeNodesParHauteur;
    stack<Node<T>*> pileDeNode;
    if(root!=NULL)
    {

        /*Algorithme de parcours en profondeur d'abord pour afficher le B-arbre à l'envers*/
        //for(size_t i=1;i<=hauteur;++i){
        /*On  place les nodes en fonction de leur hauteur dans une liste*/

        listeDeListeDeNodesParHauteur = visitNode(root,listeDeListeDeNodesParHauteur,hauteur);
        /*On affiche la liste en fonction des hauteurs*/
        for (typename vector< vector<Node<T>*> >::iterator itListeDeListe = listeDeListeDeNodesParHauteur.begin(); itListeDeListe!=listeDeListeDeNodesParHauteur.end(); ++itListeDeListe)
        {

            for (typename vector<Node<T>*>::iterator itListeNode = (*itListeDeListe).begin(); itListeNode!=(*itListeDeListe).end(); ++itListeNode)
            {
                for (typename vector<pNode<T>*> ::iterator itPNode = (*itListeNode)->getPNodesVector().begin(); itPNode!=(*itListeNode)->getPNodesVector().end(); ++itPNode)
                {
                    if((*itPNode)->getValeur()!=-1)
                    {
                        cout <<  (*itPNode)->getValeur() << "|";
                    }
                }
                cout << "      " ;
            }
            cout<<endl;
        }
    }
    else
    {
        cout<< "Le B-arbre est vide" <<endl;
    }
}

/*Méthode qui visite les fils d'un Node puis une fois finie, rajoute le node dans listeDeListeDeNodesParHauteur à l'index de la hauteur correspondante.*/

template<class T,class Compare>
vector< vector<Node<T>*> > BArbre<T,Compare>::visitNode(Node<T>* node, vector< vector<Node<T>*> > listeDeListeDeNodesParHauteur, unsigned int hauteur)
{
    if(listeDeListeDeNodesParHauteur.size()<=hauteur)
    {
        vector<Node<T>*> listeDeNodes;

        listeDeListeDeNodesParHauteur.push_back(listeDeNodes);
    }
    /*On visite les fils, donc la hauteur augmente de 1*/

    for (ItePNode it = node->getPNodesVector().begin(); it!=node->getPNodesVector().end(); ++it)
    {
        /*TODO : problème de test de pointeur égal a null/0*/

        if((*it)->getPointeur())
        {
            listeDeListeDeNodesParHauteur = visitNode((*it)->getPointeur(),listeDeListeDeNodesParHauteur,hauteur+1);
        }

    }
    /*On ajoute le Node visité à la liste de Node de la hauteur correspondante.*/
    listeDeListeDeNodesParHauteur.at(hauteur).push_back(node);
    return listeDeListeDeNodesParHauteur;
}

/*
	Renvoie 1 si la suppression s'est faite et 0 sinon.
*/

template<class T,class Compare>
int BArbre<T,Compare>::deleteNode(T key)
{

    /*étape 1 : on cherche le node ou se trouve la valeur k. Si on ne le trouve pas on renvoie 0*/
    PNodeIT nodeWithValueToDeleteIT=this->getNodeByKeyRec(root,key);

    if(!nodeWithValueToDeleteIT)
    {
        cout<<"La node a delete n'existe pas"<<endl;
        return 0;
    }
    else
    {

        //le noeud est une feuille.
        if(!nodeWithValueToDeleteIT->getPNode()->getPointeur())
        {
            ItePNode iterPnodes;
            //si après l'hypotétique suppression, le noeud feuille respecte l'ordre minimal, alors on peux supprimer simplement la clé k
            if(nodeWithValueToDeleteIT->getSizePnodeVector()-1>=order)
            {
                nodeWithValueToDeleteIT->removePNodeFromVector(key);
                return 1;

            }
            //si après l'hypotétique suppression, le noeud ne respecte pas l'ordre minimal, alors on récupère une clé d'un frère ou s'ils n'en n'ont pas, du père.
            else
            {
                recupererCle(nodeWithValueToDeleteIT,key);


            }
        //le noeud est interne. On permute avec la clé la plus à droite dans le sous arbre gauche de la clé à supprimer ou avec la clé la plug à gauche du sous-arbre droit. Puis on supprime la clé.
        }else{
            permuterCle(nodeWithValueToDeleteIT,key);

        }
    }

    return 0;
}

//méthode qui donne une clé au node où on a supprimé une valeur.
template<class T,class Compare>
void BArbre<T,Compare>::permuterCle(PNodeIT nodeWithValueToDeleteIT,T key)
{
    PNode cleASupprimer = nodeWithValueToDeleteIT->getPNode();
    PNode cleAMonter;

    //la clé à supprimer a un sous-arbre gauche
    if(nodeWithValueToDeleteIT->getPNode()->getPointeur()){
        cleAMonter = cleASupprimer->getPointeur()->getLastPNode();
    }else{
        ItePNode it = nodeWithValueToDeleteIT->getIter()+1;
        cleAMonter = (*it)->getPointeur()->getLastPNode();
    }

    //on permute

    cleAMonter->setPointeur(cleASupprimer->getPointeur());

    nodeWithValueToDeleteIT->getNode()->getPNodesVector().insert(nodeWithValueToDeleteIT->getIter(),cleAMonter);
    nodeWithValueToDeleteIT->getNode()->getPNodesVector().erase(nodeWithValueToDeleteIT->getIter()+1);

    recupererCle(this->getNodeByKeyRec(root,key),key);


}

//méthode qui donne une clé au node où on a supprimé une valeur.
template<class T,class Compare>
void BArbre<T,Compare>::recupererCle(PNodeIT nodeWithValueToDeleteIT,T key)
{

    ItePNode iteToPositionPnodeParent = nodeWithValueToDeleteIT->getNode()->getIteToPositionPnodeParent();
    Node<T>* nodeParent = nodeWithValueToDeleteIT->getNode()->getParent();
    ItePNode cleADescendreDuPereIte;

    //soit le frère gauche a une clé à passer au père, on récupère donc sa clé.
    Node<T>* frereGauche = getFrereGauche(nodeParent,iteToPositionPnodeParent);

    if(frereGauche&&frereGauche->getNbK()>order)
    {
        //on se positionne sur le pNode qui contient le pointeur vers le frère gauche.
        --iteToPositionPnodeParent;

        monterCleDuFrereGauche(nodeParent,(*iteToPositionPnodeParent)->getPointeur(),iteToPositionPnodeParent);
        ++iteToPositionPnodeParent;

        //on rafraichit l'iterateur sur les pNodes du père du Node dont on supprime une clé
        nodeWithValueToDeleteIT = this->getNodeByKeyRec(root,key);
        cleADescendreDuPereIte=nodeWithValueToDeleteIT->getNode()->getIteToPositionPnodeParent();
        //on se place sur le pNode à descendre
        --cleADescendreDuPereIte;

        //on met à jour le pointeur gauche de la clé passée au père
        ItePNode cleMonterDeFrere = cleADescendreDuPereIte-1;
        (*cleMonterDeFrere)->setPointeur((*cleADescendreDuPereIte)->getPointeur());

        //on descent la clé du père
        descendreCleDuPereDeFrereGauche(cleADescendreDuPereIte,nodeWithValueToDeleteIT);

    }
    //soit le frère droit a une clé à passer au père, on récupère donc sa clé.
    else
    {
        Node<T>* frereDroit = getFrereDroit(nodeParent,iteToPositionPnodeParent);
        if(frereDroit&&frereDroit->getNbK()>order)
        {
            //on se positionne sur le pNode qui contient le pointeur vers le frère droit.
            ++iteToPositionPnodeParent;

            monterCleDuFrereDroit(nodeParent,(*iteToPositionPnodeParent)->getPointeur(),iteToPositionPnodeParent);

            --iteToPositionPnodeParent;
afficherArbre();
            //on rafraichit l'iterateur sur les pNodes du père du Node dont on supprime une clé
            cleADescendreDuPereIte=this->getNodeByKeyRec(root,key)->getNode()->getIteToPositionPnodeParent();

            //on met à jour le pointeur gauche du pnode remonté.
            Node<T>* pointeurGauche = (*cleADescendreDuPereIte)->getPointeur();

            ++cleADescendreDuPereIte;

            (*cleADescendreDuPereIte)->setPointeur(pointeurGauche);

            --cleADescendreDuPereIte;
afficherArbre();
//on rafraichit l'iterateur sur les pNodes du père du Node dont on supprime une clé
        nodeWithValueToDeleteIT = this->getNodeByKeyRec(root,key);

            //on descent la clé parent
            descendreCleDuPereDeFrereDroit(cleADescendreDuPereIte,nodeWithValueToDeleteIT);

        }else{
            if(frereDroit){
                descendreCleDuPere(nodeWithValueToDeleteIT,1);

            }else{
                descendreCleDuPere(nodeWithValueToDeleteIT,0);
            }

        }
    }



}

template<class T,class Compare>
void BArbre<T,Compare>::descendreCleDuPere(PNodeIT nodeWithValueToDeleteIT, bool haveFrereDroit)
{
    ItePNode pNodeToDeleteIte=nodeWithValueToDeleteIT->getIter();
    //PNode pNodeToDelete=(*pNodeToDeleteIte);
    //on supprime le pnode à descendre du père
    nodeWithValueToDeleteIT->setIter(nodeWithValueToDeleteIT->getNode()->getPNodesVector().erase(pNodeToDeleteIte));


    //on met le pointeur du père à null
    (*pNodeToDeleteIte)->setPointeur(0);


    //on fusionne avec le fils gauche ou droite
    if(haveFrereDroit){

    }else{

    }

    //On vérifie que le noeud du père respecte l'ordre récursivement.

}

template<class T,class Compare>
void BArbre<T,Compare>::descendreCleDuPereDeFrereGauche(ItePNode cleADescendreDuPereIte,PNodeIT nodeWithValueToDeleteIT)
{
    ItePNode pNodeToDeleteIte=nodeWithValueToDeleteIT->getIter() ;

    //on met à jour le pointeur du pNode qui provient du père en fonction du pointeur du pNode qu'on supprime.
    (*cleADescendreDuPereIte)->setPointeur(nodeWithValueToDeleteIT->getPNode()->getPointeur());

    //on supprime le pNode contenant la valeur à supprimer.
    nodeWithValueToDeleteIT->getNode()->getPNodesVector().erase(nodeWithValueToDeleteIT->getIter());

    //on insère le pNode venant du père à la première place.
    pNodeToDeleteIte= nodeWithValueToDeleteIT->getNode()->getPNodesVector().insert(nodeWithValueToDeleteIT->getNode()->getPNodesVector().begin(),(*cleADescendreDuPereIte));

    //on supprime le pNode descendu dans le père.
    nodeWithValueToDeleteIT->getNode()->getParent()->getPNodesVector().erase(nodeWithValueToDeleteIT->getNode()->getIteToPositionPnodeParent()-1);
}

template<class T,class Compare>
void BArbre<T,Compare>::descendreCleDuPereDeFrereDroit(ItePNode cleADescendreDuPereIte,PNodeIT nodeWithValueToDeleteIT)
{
    ItePNode pNodeToDeleteIte=nodeWithValueToDeleteIT->getIter() ;

    //on met à jour le pointeur du pNode qui provient du père en fonction du pointeur du pNode qu'on supprime.
    (*cleADescendreDuPereIte)->setPointeur(nodeWithValueToDeleteIT->getPNode()->getPointeur());

    //on supprime le pNode contenant la valeur à supprimer.
    nodeWithValueToDeleteIT->getNode()->getPNodesVector().erase(nodeWithValueToDeleteIT->getIter());

    //on insère le pNode venant du père à la dernière place.
    pNodeToDeleteIte = nodeWithValueToDeleteIT->getNode()->getPNodesVector().insert(nodeWithValueToDeleteIT->getNode()->getPNodesVector().end()-1,(*cleADescendreDuPereIte));    //on supprime le pNode dans le père.
    afficherArbre();
    nodeWithValueToDeleteIT->getNode()->getParent()->getPNodesVector().erase(--nodeWithValueToDeleteIT->getNode()->getIteToPositionPnodeParent());

}




template<class T,class Compare>
void BArbre<T,Compare>::monterCleDuFrereGauche(Node<T>* nodeParent,Node<T>* frere, ItePNode iteToPositionPnodeParent)
{

    //on place un itérateur sur la dernière clé du node.
    ItePNode itPNode = frere->getPNodesVector().begin();
    while((*itPNode)->getValeur()!=-1){
        ++itPNode;
    }
    //on se place sur le dernier pNode du frère
    --itPNode;

    //on fait pointer le pointeur qu'on va passer au père sur

    //on insère dans le père le dernier pNode du frère à la bonne place par rapport à l'ordre.
    nodeParent->getPNodesVector().insert(iteToPositionPnodeParent,(*itPNode));
    //on supprime le pNode dans le frère
    frere->getPNodesVector().erase(itPNode);


}

template<class T,class Compare>
void BArbre<T,Compare>::monterCleDuFrereDroit(Node<T>* nodeParent,Node<T>* frere,ItePNode iteToPositionPnodeParent)
{

    //on place un itérateur sur la première clé du node.
    ItePNode itPNode = frere->getPNodesVector().begin();

    //on insère dans le père le dernier pNode du frère à la bonne place par rapport à l'ordre.
    nodeParent->getPNodesVector().insert(iteToPositionPnodeParent,(*itPNode));

    //on supprime le pNode dans le frère
    frere->getPNodesVector().erase(itPNode);


}


template<class T,class Compare>
Node<T>* BArbre<T,Compare>::getFrereGauche(Node<T>* nodeParent,ItePNode iteToPositionPnodeParent)
{
    ItePNode pIt = nodeParent->getPNodesVector().end();
    //on se positionne sur le parent du node dont on supprime une clé
    while((*pIt)!= (*iteToPositionPnodeParent)){
        --pIt;
    }
    //on vérifie qu'on est pas au début.
    if(pIt==nodeParent->getPNodesVector().begin()){
        return 0;
    }

    //on se place sur le frère gauche juste après
    --pIt;

    //on se déplace sur le fils du frère gauche du père.
    return (*pIt)->getPointeur();

}

template<class T,class Compare>
Node<T>* BArbre<T,Compare>::getFrereDroit(Node<T>* nodeParent,ItePNode iteToPositionPnodeParent)
{
    ItePNode pIt = nodeParent->getPNodesVector().begin();
    //on se positionne sur le parent du node dont on supprime une clé
    while((*pIt)!= (*iteToPositionPnodeParent)){
        ++pIt;
    }

    //on vérifie qu'on est pas au début.
    if(pIt==nodeParent->getPNodesVector().end()){
        return 0;
    }

    //on se place sur le frère droit juste après
    ++pIt;

    //on se déplace sur le fils du frère droit du père.
    return (*pIt)->getPointeur();
}

template<class T,class Compare>
void BArbre<T,Compare>::setRoot(Node<T> * r)
{
    root=r;
}

template<class T,class Compare>
Node<T> * BArbre<T,Compare>::getRoot()
{
    return root;
}

template<class T,class Compare>
unsigned int BArbre<T,Compare>::getHauteur()
{
    return this->hauteur;
}

template<class T,class Compare>
NodeIT<T>* BArbre<T,Compare>::search(T key)
{
    return getNodeByKeyRec(root, key);
}

template<class T,class Compare>
BNodeIter<T> BArbre<T,Compare>::begin(){
	BNodeIter<T> it= BNodeIter<T>(this);
	return  it;
}
template<class T,class Compare>
BNodeIter<T> BArbre<T,Compare>::end(){
	BNodeIter<T> it= BNodeIter<T>(this);
	while (*it!=0){
		it++;	
	}
	return  it;
}
#endif

